package _17_剑指Offer;

import _17_剑指Offer.datastrcute.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class _68_剑指OfferI二叉搜索树的最近公共祖先 {

    // 递归
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }

    // 一次遍历
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }

    // 找到p，或者q的搜索路径。然后比较搜索路径中最先的某个值是否相同
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        // 搜索p,q的路径
        List<TreeNode> pPath = getPath(root, p);
        List<TreeNode> qPath = getPath(root, q);
        // 查找相同路径
        int pSize = pPath.size();
        int qSize = qPath.size();
        TreeNode ancestor = null;
        for (int i = 0; i < pSize && i < qSize; i++) {
            if (pPath.get(i) == qPath.get(i)) {
                ancestor = pPath.get(i);
            } else {
                break;
            }
        }
        return ancestor;
    }

    private List<TreeNode> getPath(TreeNode root, TreeNode p) {
        List<TreeNode> list = new ArrayList<>();
        while (true) {
            list.add(root);
            if (root.val > p.val) {
                root = root.left;
            } else if (root.val < p.val) {
                root = root.right;
            } else {
                return list;
            }
        }
    }


}
